package Offer;

import java.util.*;

/**
 * 从上到下打印二叉树 III
 *
 * @author 是阿秋啊
 * @date 2022/04/04 21:33
 **/
public class Num32III {
    // 方法一：层序遍历 + 双端队列
    public List<List<Integer>> levelOrder1(TreeNode root) {
        List<List<Integer>> ret = new ArrayList<>();
        Deque<TreeNode> deque = new ArrayDeque<>();
        if (root != null) {
            deque.offer(root);
        }
        int flag = 1;
        while (!deque.isEmpty()) {
            int size = deque.size();
            LinkedList<Integer> cur = new LinkedList<>();
            for (int i = 0; i < size; i++) {
                TreeNode node = deque.poll();
                if (flag % 2 != 0) {
                    cur.addLast(node.val);
                } else {
                    cur.addFirst(node.val);
                }
                if (node.left != null) {
                    deque.offer(node.left);
                }
                if (node.right != null) {
                    deque.offer(node.right);
                }
            }
            ret.add(cur);
            flag++;
        }
        return ret;
    }

    // 方法二：层序遍历 + 双端队列（奇偶层逻辑分离）
    public List<List<Integer>> levelOrder2(TreeNode root) {
        List<List<Integer>> ret = new LinkedList<>();
        Deque<TreeNode> deque = new LinkedList<>();
        if (root != null) {
            deque.add(root);
        }
        int flag = 1;
        while (!deque.isEmpty()) {
            List<Integer> cur = new LinkedList<>();
            int size = deque.size();
            if (flag % 2 != 0) {
                for (int i = 0; i < size; i++) {
                    TreeNode node = deque.removeFirst();
                    cur.add(node.val);
                    // 先左后右加入下层节点
                    if (node.left != null) {
                        deque.addLast(node.left);
                    }
                    if (node.right != null) {
                        deque.addLast(node.right);
                    }
                }
            } else {
                for (int i = 0; i < size; i++) {
                    TreeNode node = deque.removeLast();
                    cur.add(node.val);
                    // 先右后左加入下层节点
                    if (node.right != null) {
                        deque.addFirst(node.right);
                    }
                    if (node.left != null) {
                        deque.addFirst(node.left);
                    }
                }
            }
            flag++;
            ret.add(cur);
        }
        return ret;
    }
    // 方法三：层序遍历 + 倒序
    public List<List<Integer>> levelOrder3(TreeNode root) {
        List<List<Integer>> ret = new LinkedList<>();
        Deque<TreeNode> deque = new LinkedList<>();
        if (root != null) {
            deque.offer(root);
        }
        while (!deque.isEmpty()) {
            int size = deque.size();
            List<Integer> cur = new LinkedList<>();
            for (int i = 0; i < size; i++) {
                TreeNode node = deque.poll();
                cur.add(node.val);
                if (node.left != null) {
                    deque.offer(node.left);
                }
                if (node.right != null) {
                    deque.offer(node.right);
                }
            }
            if (ret.size() % 2 == 1) {
                Collections.reverse(cur);
            }
            ret.add(cur);
        }
        return ret;
    }
}
